基本信息

  • 论文： The Sprawlter Graph Readability Metric: Combining Sprawl and Area-aware Clutter
  • 作者： Zipeng Liu, Takayuki Itoh, Jessica Q. Dawson, and Tamara Munzner
  • 来源： IEEE TVCG 2020.

动机

  • 构造自动布局方法需要评价标准
  • 可视化的信达雅
    • 信-忠实：从数据转化到可视表示时不歪曲，不误导，不遗漏。
    • 达-有用：可视化的表现方式自然有效，清楚易用，容易上手，帮助用户达成目标。—对应—>可读性
    • 雅-优美：系统充满美感，给用户优雅的体验。
  • 已有指标缺点
    • 整数限制 (e.g., 统计点和边之间的交叉次数)
    • 单一层级，不考虑多层级（e.g., 子图结构）
    • 只关注是否杂乱，不考虑布局质量 (e.g., 节点无限小，边无限细可以减少重叠)

方法——可读性指标构造

  • 概览
    • 引入面积意识来评价杂乱程度
    • 引入元节点来拓展层级意识
    • 提出 sprawlter 指标来综合评价蔓延程度和杂乱程度

  • 几何特征映射到惩罚因子

    avatar

    • 节点-节点：重叠面积
    • 节点-边：重叠长度
    • 边-边：角度

  • 构造惩罚因子到杂乱指标的映射函数

    • 需求
      • 严格递增的单调函数：$\forall x_1<x_2, f(x_1)<f(x_2)$
      • 触发即重大（区分重叠很小和没有重叠）：$f(0)>>0$
      • 计数校准（显示比整数更复杂的信息）：$minPenalty<1<maxPenalty$
      • 局部适用（可以评价一对节点，一对边或点边）：是$f_{v_1,v_2}^{NN}(x)$而不止是$f_G^{NN}(x)$
    • 函数构造：$f(x)=(\beta-\alpha)x^\gamma+\alpha M^\gamma (0\leqslant x \leqslant M)$

    avatar

    • 参数解释
      • $\alpha$：指标最小值
      • $\beta$：指标最大值
      • $M$：潜在最大值（e.g.,一个节点的大小是点点重叠的潜在最大值）
      • $\gamma$：弯曲形状（推荐值：NN-0.7；NE-1；EE-2）
      • avatar

  • 考虑蔓延程度（只对节点对有效）

    • 计算覆盖比例：$S(G)=area(G)/area(\bigcup_{v\in V^\mathcal{V}})$
    • 混合蔓延程度和杂乱程度：$T^{NN}(G)=\sqrt{S(G)\dot max{ A^{NN}(G), 1}}$

  • 例子

    avatar

评估

  • 评价对象：38 个合成图（包括力引导自造小图和不同布局算法得出的大图）+18 个真实图布局
  • 对比方案
    • A：考虑面积的杂乱程度指标（本文提出）
    • C：计数统计
    • S：蔓延比例（本文提出）
    • T：Sprawlter 指标（本文提出）
    • D：Dunne 等人提出的，计算当前可读性/最优可读性的$[0,1]$指标
  • （结果图可见原文）
  • 结论：本文提出的指标可以更准确地反映人的评价

Questions & Discussion： ✉️ wangxumeng@zju.edu.cn